The Internet and communications or data networks in general have become key enablers to a broad range of business, government, and personal activities. More and more, such networks are being used as a general information appliance, business communication tool, entertainment source, and also a substitute for traditional telephone networks and broadcast media.
Traffic placement deals with the selection of, and the routing of customer traffic flows (demands) over a particular physical topology. The issue is, given a set of traffic flow demands that are candidates for placement over the network topology, to select a subset from this set that represents the “placed” traffic demands (i.e. the demands that will be actually carried over the network, which may be the entire given set or some subset) and to compute for the placed demands a set of paths. The selected demands and the paths chosen for them should be such that network utilisation or other network characteristics are optimized, and, in cases where the demands cannot all be satisfactorily placed over the network, such that selection criteria are optimized such as the quantity and/or value of placed traffic. Note that traffic placement enapsulates routing but not vice versa since traffic placement is concerned additionally with the selection of the traffic flows that are routed over the network.
Generally, a communications network consists of nodes and links. A demand is defined by its source and destination node and usually also by a certain bandwidth requirement. Other requirements may include a given maximum path delay or a demand cost penalty that is incurred for not placing the demand, for example. The paths that carry traffic under normal operating conditions are known as “primary paths”.
However, traffic placement problems may also incorporate mechanisms that protect traffic against network failures. This involves the calculation of pre-configured backup paths that ensure traffic flows can still be carried over the network in the event of single or multiple link or node failures.
Different schemes for protection using pre-configured backup paths are in existence. For example path protection for a demand involves the computation of an alternative “secondary path” from the demand's source to its destination. The secondary path remains inactive until a network failure occurs that disrupts the demand's primary path, at which point it gets activated. If the secondary path has been calculated to avoid the failed element(s) that caused the primary path to be disrupted, it will be capable of carrying traffic over the network even after the failure, thereby providing protection against this failure scenario. Note that the primary and secondary paths for a given traffic demand are interdependent under path protection schemes, because they need to avoid traversing the same failure-prone elements.
In another class of protection scheme, known as local protection (for example, in MPLS networks detour or fast re-route protection are instances of local protection) traffic is not rerouted from the source to the destination. Instead, when it arrives in the vicinity of the failed element(s), traffic is rerouted locally around the point or points of failure.
Another possible feature of traffic placement, known as “load balancing” involves the calculation of multiple paths for single traffic demands such that the multiple paths collectively carry the demand's required bandwidth over the network. Load balancing can apply in normal and/or failure protection scenarios.
Traffic placement problems are traditionally approached using techniques based on linear programming (LP) such as the Mixed Integer Programming (MIP) techniques, or using Shortest Path First (SPF) or Constraint Shortest Path First (CSPF) based techniques. However, these approaches suffer from several disadvantages and/or limitations.
MIP and other traditional LP-based approaches are impractical for solving the full traffic placement problem, as a large amount of memory is required even for relatively small problems.
As an example, consider a network that has around 700 links. Suppose that 1000 flows are to be placed. To model this using a multicommodity flow model, a variable is needed for each flow on each link. This means 700,000 variables are needed to model just this part of the problem. Alternatively, if a path variable is used to represent each potential route, the size of the problem is even greater. Both these alternative formulations lead to impractically large LP matrices and consequently to an unacceptable memory requirement.
One approach to this problem is column generation, which incrementally expands the LP (variable and constraint) matrix (see C. Barnhart, C. A. Hane, P. H. Vance, “Using Branch-and-Price-and-Cut to solve origin-destination integer multi-commodity flow problems”, Operations Research, 2000). However, while reducing the severity of this problem column generation continues to suffer from scalability limitations.
Another factor is that MIP and other traditional LP-based approaches are inflexible since they accept only certain classes of constraint. This impedes the extension of the traffic placement model to take into account new requirements.
With respect to SPF & CSPF algorithms, their weakness lies in that they are incomplete and have a low coverage of the search space. This means that, for many problem instances, they will miss acceptable or good quality solutions.